package leetcode_700;

import java.util.ArrayList;
import java.util.List;

import helpclass.TreeNode;

/**
 *@author 周杨
 *PrintBinaryTree_655 根据高度打印一颗二叉树
 *describe:简单题 递归就行 先判断高度  AC 9%
 *2018年9月27日 下午2:13:48
 */
public class PrintBinaryTree_655 {
	 public List<List<String>> printTree(TreeNode root) {
	        List<List<String>> res = new ArrayList<>();
	        if(root == null) return res;
	        int height = getHeight(root);
	        int cols = (int)Math.pow(2, height) - 1;
	        int rows = height;
	        initialize(res, rows, cols);
	        print(root, res, 0, 0, cols-1);
	        return res;
	    }
	    
	    private void print(TreeNode root, List<List<String>> res, int row, int colStart, int colEnd) {
	        if(root == null) return;
	        int mid = colStart + (colEnd - colStart)/2;
	        res.get(row).set(mid, "" + root.val);
	        print(root.left, res, row+1, colStart, mid-1);
	        print(root.right, res, row+1, mid+1, colEnd);
	    }
	    
	    private int getHeight(TreeNode root) {
	        if(root == null) return 0;
	        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
	    }
	    
	    private void initialize(List<List<String>> res, int rows, int cols) {
	        for(int i=0;i<rows;i++) {
	            res.add(new ArrayList<String>(cols));
	        }
	        for(int i=0;i<rows;i++) {
	            List<String> l = res.get(i);
	            for(int j=0;j<cols;j++) {
	                l.add("");
	            }
	        }
	    }
}
